#include "./sortdatatype.h"

// 冒泡排序
/**
 * 思想: 相邻元素间比较交换, 关键字较小的元素逐渐从底部移向顶部
 *
 * 时间复杂度为 O(N^2)
 * 空间复杂度为 O(1)
 *
 * 最坏情况时间复杂度为 O(N^2)
 * 最佳情况的时间复杂度为 O(N)
 */
void bubbleSort(SeqList R, int len)
{
    RecType temp;
    int flag; // 用来优化排序的
    // 需要比较 n-1 趟
    for (int i = 1; i < len; i++)
    {
        printf("====>step: %d, array: ", i);
        printSeqList(R, len);
        flag = 0;
        for (int j = 0; j < len - i; j++)
        {
            printf(">>compare: %d, %d  array: ", R[j].key, R[j + 1].key);
            printSeqList(R, len);
            // 升序排序
            if (R[j].key > R[j + 1].key)
            {
                temp = R[j];
                R[j] = R[j + 1];
                R[j + 1] = temp;
                flag = 1;
            }
        }

        if (flag == 0)
            break;
    }
}

// 双向冒泡排序
void doubleBubbleSort(SeqList R, int len)
{

    RecType temp;
    int flag;

    int left = 0;
    int right = len - 1;

    while (left < right)
    {
        flag = 0;
        // 正向冒泡, 从左往右
        for (int i = left; i < right; i++)
        {
            // 找到剩下中最大的
            if (R[i].key > R[i + 1].key)
            {
                temp = R[i];
                R[i] = R[i + 1];
                R[i + 1] = temp;
                flag = 1;
            }
        }
        // 已经是有序
        if (flag == 0)
            break;

        right--;

        // 反向冒泡
        for (int i = right; i > left; i--)
        {
            // // 找到剩下中最小的
            if (R[i].key < R[i - 1].key)
            {
                temp = R[i];
                R[i] = R[i - 1];
                R[i - 1] = temp;
            }
        }
        left++;
    }
}

// 快速排序(划分交换排序), 是对冒泡排序的改进，不稳定
/**
 * 思想: 通过选择一个基准元素,将数排序分成两部分,使得左边的元素小于等于基准元素,右边的元素大于基准元素,
 * 然后对两部分分别进行递归排序
 *
 * 时间复杂度为 O(N*log2N)
 * 空间复杂度为 根据实现方式的不同而不同
 *
 * 最坏情况时间复杂度为 O(N^2)
 * 最佳情况的时间复杂度为 O(N*logN)
 */
int partition(SeqList R, int low, int high);
void quickSort(SeqList R, int low, int high)
{
    if (low > high)
        return;

    int pivotIndex = partition(R, low, high);
    quickSort(R, low, pivotIndex - 1);
    quickSort(R, pivotIndex + 1, high);
}

int partition(SeqList R, int low, int high)
{
    RecType temp;
    // 选择最右边的元素为基准
    int pivot = R[high].key;
    int i = low - 1;

    for (int j = low; j < high; j++)
    {
        if (R[j].key < pivot)
        {
            i++;
            temp = R[i];
            R[i] = R[j];
            R[j] = temp;
        }
    }

    temp = R[i + 1];
    R[i + 1] = R[high];
    R[high] = temp;

    return i + 1;
}

void newQuickSort(SeqList R, int low, int high)
{
    int left = low;
    int right = high;

    int povit = R[low].key;

    while (left < right)
    {
        while (left < right && R[right].key >= povit)
            right--;

        if (left < right)
        {
            R[left] = R[right];
            left++;
        }

        while (left < right && R[left].key <= povit)
            left++;

        if (left < right)
        {
            R[right] = R[left];
            right--;
        }
    }

    R[left].key = povit;

    if (left - 1 > low)
        newQuickSort(R, low, left - 1);
    if (right + 1 < high)
        newQuickSort(R, right + 1, high);
}

int main()
{
    int arr[] = {57, 36, 28, 45, 13, 67, 36, 18, 56};
    // int arr[] = {67, 56, 45, 36, 35, 28, 18, 13};
    int len = sizeof(arr) / sizeof(arr[0]);
    SeqList R;
    init(R, arr, len);
    printf("-------------bubbleSort---------------\n");
    bubbleSort(R, len);
    printSeqList(R, len);

    init(R, arr, len);
    printf("\n-------------quickSort---------------\n");
    quickSort(R, 0, len - 1);
    printSeqList(R, len);

    init(R, arr, len);
    printf("\n-------------newQuickSort---------------\n");
    newQuickSort(R, 0, len - 1);
    printSeqList(R, len);

    return 0;
}